package thinkingInJava.containers;

//: containers/SimpleHashMap.java
//A demonstration hashed Map.
import java.util.*;

public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
// Choose a prime number for the hash table
// size, to achieve a uniform distribution:
public static final int SIZE = 997;
// You can't have a physical array of generics,
// but you can upcast to one:
@SuppressWarnings("unchecked")
public LinkedList<MapEntry<K,V>>[] buckets =
 new LinkedList[SIZE];
public V put(K key, V value) {
 V oldValue = null;
 int index = Math.abs(key.hashCode()) % SIZE;
 if(buckets[index] == null)
   buckets[index] = new LinkedList<MapEntry<K,V>>();
 LinkedList<MapEntry<K,V>> bucket = buckets[index];
 MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
 boolean found = false;
 ListIterator<MapEntry<K,V>> it = bucket.listIterator();
 while(it.hasNext()) {
   MapEntry<K,V> iPair = it.next();
   if(iPair.getKey().equals(key)) {
     oldValue = iPair.getValue();
     it.set(pair); // Replace old with new
     found = true;
     break;
   }
 }
 if(!found)
   buckets[index].add(pair);
 return oldValue;
}
public V get(Object key) {
 int index = Math.abs(key.hashCode()) % SIZE;
 if(buckets[index] == null) return null;
 for(MapEntry<K,V> iPair : buckets[index])
   if(iPair.getKey().equals(key))
     return iPair.getValue();
 return null;
}
public Set<Map.Entry<K,V>> entrySet() {
 Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
 for(LinkedList<MapEntry<K,V>> bucket : buckets) {
   if(bucket == null) continue;
   for(MapEntry<K,V> mpair : bucket)
     set.add(mpair);
 }
 return set;
}
@SuppressWarnings("unchecked")
public void clear() {
	// Effectively erase everything by allocating
	// a new empty array of buckets:
	buckets = new LinkedList[SIZE];
}
public V remove(Object key) {
	// Code is copied from get(), except that
	// before returning the value, the Map.Entry is
	// removed from the list:
	int index = Math.abs(key.hashCode()) % SIZE;
	if(buckets[index] == null) return null;
	Iterator<MapEntry<K,V>> it = buckets[index].iterator();
	while(it.hasNext()) {
		MapEntry<K,V> iPair = it.next();
		if(iPair.getKey().equals(key)) {
			// Changes are here:
			V value = iPair.getValue();
			// Removes the last fetched value:
			it.remove();
			return value;
		}
	}
	return null;
}
public static void testRemove(){
	SimpleHashMap<String,String> m =
			new SimpleHashMap<String,String>();
	m.putAll(Countries.capitals(10));
	System.out.println(m);
	System.out.println("m.get(\"BURUNDI\") = "
			+ m.get("BURUNDI"));
	m.remove("BURUNDI");
	System.out.println(
			"After removal, m.get(\"BURUNDI\") = "
					+ m.get("BURUNDI"));
	m.clear();
	System.out.println("After clearing: " + m);
}
public static void main(String[] args) {
 Map<String,String> m = new SimpleHashMap<String,String>();
 m.putAll(Countries.capitals(25));
 System.out.println(m);
 System.out.println(m.get("ERITREA"));
 System.out.println(m.entrySet());
}
} /* Output:
{CAMEROON=Yaounde, CONGO=Brazzaville, CHAD=N'djamena, COTE D'IVOIR (IVORY COAST)=Yamoussoukro, CENTRAL AFRICAN REPUBLIC=Bangui, GUINEA=Conakry, BOTSWANA=Gaberone, BISSAU=Bissau, EGYPT=Cairo, ANGOLA=Luanda, BURKINA FASO=Ouagadougou, ERITREA=Asmara, THE GAMBIA=Banjul, KENYA=Nairobi, GABON=Libreville, CAPE VERDE=Praia, ALGERIA=Algiers, COMOROS=Moroni, EQUATORIAL GUINEA=Malabo, BURUNDI=Bujumbura, BENIN=Porto-Novo, BULGARIA=Sofia, GHANA=Accra, DJIBOUTI=Dijibouti, ETHIOPIA=Addis Ababa}
Asmara
[CAMEROON=Yaounde, CONGO=Brazzaville, CHAD=N'djamena, COTE D'IVOIR (IVORY COAST)=Yamoussoukro, CENTRAL AFRICAN REPUBLIC=Bangui, GUINEA=Conakry, BOTSWANA=Gaberone, BISSAU=Bissau, EGYPT=Cairo, ANGOLA=Luanda, BURKINA FASO=Ouagadougou, ERITREA=Asmara, THE GAMBIA=Banjul, KENYA=Nairobi, GABON=Libreville, CAPE VERDE=Praia, ALGERIA=Algiers, COMOROS=Moroni, EQUATORIAL GUINEA=Malabo, BURUNDI=Bujumbura, BENIN=Porto-Novo, BULGARIA=Sofia, GHANA=Accra, DJIBOUTI=Dijibouti, ETHIOPIA=Addis Ababa]
*///:~
